package basis.netease.easy.废弃;

import java.util.Scanner;
import java.util.Stack;

/**
 * 7-30 二叉搜索树中第K小的元素
 * 给定一个二叉搜索树的根节点 root ，和一个整数 K ，请你设计一个算法查找其中第 K 个最小元素（从 1 开始计数）
 * 输入格式:
 * 树上的节点数满足 0 <= n <= 1000, 每个节点的值满足 -1000 <= val <= 1000
 * 第K个最小元素 满足 K <= 1000
 * 输出格式:
 * 第K小的节点值
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 3,1,4,null,2
 * 3
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 3
 */
public class Main_30 {

    public static int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        // 中序遍历（得到升序的值）：左子树 -> 根节点 -> 右子树
        while (current != null || !stack.isEmpty()) {
            // 先将左边界的所有节点压入栈中
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // 取出栈顶元素，即当前最小的元素
            current = stack.pop();
            // 如果这是第k个元素，返回它
            if (--k == 0) {
                return current.val;
            }
            // 转向右子树继续寻找
            current = current.right;
        }
        return 0;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int k = scanner.nextInt();
        String[] input = str.split(",");
        TreeNode root = null;
        for (String num : input) {
            if (!"null".equals(num)) {
                root = insertIntoBST(root, Integer.parseInt(num));
            }
        }
        System.out.println(kthSmallest(root, k));
    }

    private static TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }

}
